\chapter{Conclusion et futurs travaux}

Dans cette conclusion, nous allons tout d'abord examiner les objectifs de départ que nous avions fixés dans l'introduction et voir si ceux-ci sont atteints en fin de travail. Ensuite, nous allons résumer les étapes parcourues tout au long de ce travail, pour arriver à ces objectifs. Enfin, nous évoquerons quelques pistes pour de futurs travaux dans le domaine. 

\section{Conclusion}

Les objectifs de base étaient simples: partant d'un programme écrit en \textsl{dSL}, qui a été distribué dans une ancienne version, comment redistribuer une nouvelle version de ce programme de manière efficace, c'est-à-dire en essayant de garder au maximum la structure de la précédente distribution et en minimisant les transmissions possibles entre les sites. Nous sommes effectivement arrivés à une méthode de redistribution qui se déroule en trois étapes: \\

\begin{enumerate}
	\item La comparaison des deux versions du code ;
	\item La pré distribution du nouveau code ;
	\item La finition de la distribution du nouveau code.
\end{enumerate}

\bigskip
La première étape nous a permis de trouver les parties de code qui n'avaient pas changé et, dans la seconde étape, ces parties inchangées de code ont pu être distribuées comme dans l'ancienne version. La combinaison des deux premières étapes nous a donc permis de respecter le critère de conservation de la structure de distribution. Le second critère, lui, a été pris en compte dans la troisième et dernière étape qui, étant donné un coût de redistribution minimum au départ, essaie de réduire le coût de transmission tout en gardant la somme des deux coûts minimale. Ces trois étapes permettent donc de redistribuer une application de contrôle modifiée, tout en respectant les contraintes que l'on s'est imposées. \\

Pour arriver à une telle technique, il a fallu passer par plusieurs étapes d'analyse des problèmes et de définitions. Mais la toute première étape de ce travail a été l'introduction au contexte dans lequel s'inscrit ce mémoire: le contrôle industriel par le langage \textsl{dSL}. Nous avons donc vu, en tout premier lieu, ce qu'était le contrôle industriel et comment \textsl{SL}, l'ancêtre de \textsl{dSL}, pouvait nous aider à effectuer un tel contrôle. Ensuite, nous avons détaillé en quoi \textsl{dSL} est plus pratique pour développer une application de contrôle: on ne doit pas se soucier des différents sites, il suffit juste de créer une application d'un bout à l'autre, qui sera distribuée automatiquement. \\

Avant de voir la méthode de distribution automatique de code avec \textsl{dSL}, il a fallu énoncer les principaux éléments de syntaxe du langage et comment chacun devait se comporter dans le processus de distribution (code atomique ou code séquentiel). Après ces analyses du langage, le problème de la distribution automatique a été décrit et une solution provenant de~\cite{BDeW} a été expliquée. Cette méthode de distribution fonctionne en deux étapes et sépare la distribution du code atomique, de la distribution du code séquentiel. La première étape utilise la table de localisation pour distribuer une grande partie du code, tandis que la seconde étape s'occupe de finir la distribution en tenant compte d'un critère de performance: la minimisation des transmissions. \\

À partir de là, nous avions le bagage de connaissances nécessaires pour se lancer dans l'analyse et la résolution du problème de redistribution. Mais, avant cela, il a fallu motiver la recherche d'une telle solution à un tel problème: pourquoi ne pas distribuer une nouvelle version d'un programme de contrôle comme si ce n'était pas une modification d'une ancienne version ? C'est la solution qui était adoptée jusqu'à présent, mais qui ne convient pas pour les programmeurs. En effet, sur des grosses applications, les programmeurs savent où se trouvent les différentes instructions et peuvent facilement faire des diagnostics en cas de problème. Lorsqu'une nouvelle version d'une application est réalisée et distribuée, la structure de distribution pourrait changer. Dès lors, les programmeurs n'auraient plus cette connaissance de la structure et les diagnostics ne se feraient pas aussi rapidement. Pour résumer la motivation, c'est principalement la conservation de la structure (afin de permettre des résolutions de \textsl{bugs} rapidement) qui a motivé la recherche d'une redistribution efficace. \\

Nous avons également vu que les deux critères de la redistribution étaient contradictoire. Plus on essayait d'être performant en terme de transmissions, plus la structure de distribution pourrait changer. C'est pourquoi, dans cette solution de redistribution, il est possible de paramétrer à quel niveau le programmeur veut être efficace et à quel niveau il veut conserver la structure de distribution. La meilleure solution de redistribution, nous l'avons définie comme étant celle qui possède la somme minimale des deux coûts pondérés (par des paramètres fixés par le programmeur, selon son désir) représentants les deux critères à respecter. \\

Ensuite, avant de se lancer dans la recherche pure et dure, il a fallu correctement modéliser le problème de la redistribution. C'est à ce moment là que ce problème a été séparé en deux sous-problèmes: (i) la comparaison de versions, et (ii) la redistribution de la nouvelle version. Le premier sous-problème permet d'identifier ce qui est similaire entre les deux versions de code pour pouvoir garder le site de distribution de ces instructions non-modifiées, ce qui permet, déjà, de conserver la structure de distribution. Le second sous-problème permet de distribuer l'application, en tenant compte (i) de la table de localisation, et (ii) des équivalences entre les instructions des deux versions, réalisée par la comparaison. Les deux problèmes ont alors été étudiés séparément. Ces études de problèmes ont été réalisées sur des formalisations des problèmes, sorties de leur contexte, afin d'être le plus général possible. Nous avons donc, tout d'abord, établi que ces problèmes pouvaient être vus comme des problèmes de graphes. Nous avons défini la structure des graphes pour ces deux sous-problèmes, nous avons décrit le calcul des deux coûts (redistribution et transmission) à l'aide des graphes et nous avons commencé la recherche de solutions. \\

Pour le problème de comparaison, nous avons cherché dans la littérature pour voir si un problème similaire existait. Nous avons alors découvert une pléthore de problèmes tels que les problèmes d'isomorphismes de (sous-)graphes, la recherche d'un sous-graphe commun maximum, la correspondance entre graphes par correction d'erreurs, et bien d'autres encore. La plupart de tous ces problèmes sont NP-complets et, parmi ceux-ci, il a fallu choisir celui qui correspondait le plus à notre problème de comparaison de versions. Nous avons donc retenu, finalement, le problème de la recherche de sous-graphe commun maximum comme étant celui qui se rapprochait le plus de notre problème. C'est donc avec une compréhension de celui-ci et quelques algorithmes trouvés dans la littérature que nous avons pu résoudre notre problème de comparaison. En fait, l'algorithme choisi est un algorithme pour l'isomorphisme de graphes et de sous-graphes, que nous avons légèrement adapté pour permettre de trouver le plus grand sous-graphe commun maximum. \\

Pour le problème de redistribution, notre réflexion a été la suivante: en supposant que nous avons une correspondance entre les n\oe{}uds du premier graphe et les n\oe{}uds du second, nous pouvons, avant de commencer, colorer ces n\oe{}uds avec leur ancienne couleur, ainsi que colorer les n\oe{}uds sur lesquels une contrainte de couleur est imposée. Nous obtenons donc un graphe partiellement coloré dont le coût de redistribution est déjà à son minimum puisqu'il n'y a plus que ce qui a été modifié ou ajouté à redistribuer. Le fait d'avoir gardé ces anciennes couleurs fait que la structure de distribution est effectivement conservée, mais il se peut que, dès lors, le coût de transmission ne soit plus à son minimum. Donc, la seule façon d'avoir une solution optimale est d'essayer de minimiser le coût de transmission. Nous avons établi la formule permettant la minimisation des deux coûts: 
\begin{equation*}
	min (\alpha C_r + \beta C_t)
\end{equation*}
avec $C_r$ qui est le coût de redistribution et $C_t$ qui est le coût de transmission. Cette équation nous a directement fait penser à un problème d'optimisation linéaire et c'est dans cette optique que nous avons cherché à modéliser notre problème. La solution à un tel problème, une fois modélisé, a été de recourir à un algorithme de \textsl{branch and bound} (ou par séparation et évaluation, en français) afin de trouver la solution optimale de la redistribution. \\

Après avoir énoncé et décrit les solutions aux deux sous-problèmes, nous avons remis les deux solutions ensembles dans le contexte de départ: celui du langage \textsl{dSL} avec une rapide description des étapes à réaliser, dans ce contexte. Un exemple, afin d'illustrer la méthode de redistribution, a été donné et expliqué en détail et, enfin, une implémentation a été réalisée et commentée. \\

\section{Futurs travaux}
 
La solution proposée dans ce mémoire ne constitue pas une solution ultime, dans le sens où elle est certainement améliorable. Tout d'abord, il serait peut-être possible de trouver un meilleur algorithme de comparaison et un meilleure algorithme de redistribution, afin que les complexités soient moins grandes. Bien sûr, si $P=NP$ est démontré, d'autres algorithmes qui s'exécutent en temps polynomial pourraient certainement être trouvés. \\

Mis à part le côté théorique de ce mémoire, l'implémentation peut également faire partie d'un futur travail. En effet, il serait imaginable de trouver des optimisation à cette implémentation (tant au niveau des structures de données qu'au niveau des algorithmes écrits). Également, l'implémentation réalisée ici n'est pas tout à fait finie, il reste à rendre plus complet le \textit{parsing} (très simplifié dans notre implémentation). Enfin, il faut évidemment effectuer un travail très important: l'intégration de l'implémentation dans l'outil de \textit{compilation-distribution} pour que la solution soit effectivement utilisée. \\

En résumé, il s'agit principalement de travaux d'amélioration (des algorithmes théoriques et de l'implémentation) ainsi qu'un travail de finition sur l'implémentation. Mis à part cela, nous ne voyons pas d'autres travaux dans le domaine, mais cela ne signifie pas qu'il n'y en a plus !